//
// Created by martin on 8/19/21.
//

#include "queue.h"
#include <stdlib.h>
#include <string.h>

/**
 * 创建队列
 * @return
 * - NULL 创建失败
 * - Not-NULL 创建成功，返回指向新建队列的指针
 */
Queue *queue_new()
{
    Queue *q = (Queue *)malloc(sizeof(Queue));
    if (!q) {
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;

    return q;
}

/**
 * 释放队列
 * @param q 队列对象
 */
void queue_free(Queue *q)
{
    if (!q) return;

    Node *node = q->head;
    while (node != NULL) {
        if (node->e) free(node->e);
        free(node);
        node = node->next;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;

    free(q);
}

/**
 * 队列尾插入一个元素
 * @param q 队列对象
 * @param e 待插入队列的元素内容，e需要存储在堆中
 */
int queue_offer(Queue *q, ElemType *e)
{
    if (!q) return -1;

    Node *node = (Node *) malloc(sizeof(Node));
//    memcpy(node->e, e, sizeof(ElemType));
    node->e = e;
    node->next = NULL;
    node->prev = NULL;

    if (q->head == NULL) { // 队列为空
        q->head = q->tail = node;
    }
    else {
        node->prev = q->tail;
        q->tail->next = node;
        q->tail = node;
    }

    q->size++;
    return 0;
}

/**
 * 返回并移除队列的头
 * @param q 队列对象
 * @return 移除的头部元素
 */
ElemType *queue_poll(Queue *q)
{
    if (!q || !q->head) return NULL;
    ElemType *e = q->head->e;
    Node *head = q->head;

    if (q->head->next == NULL) { // 只有一个节点
        q->head = q->tail = NULL;
    }
    else { // >= 2个节点
        q->head->next->prev = NULL;
        q->head = q->head->next;
    }
    free(head); // 释放head节点，单未释放存储的元素

    q->size--;
    return e;
}

/**
 * 返回但不移除队列的头
 * @param q 队列对象
 * @return 头部元素
 */
ElemType *queue_peek(Queue *q)
{
    if (!q || !q->head) return NULL;

    return q->head->e;
}

/**
 * 返回队列元素个数
 * @param q 队列对象
 * @return 队列中元素个数
 */
size_t queue_size(Queue *q)
{
    if (!q || !q->head) return 0;

    return q->size;
}